package com.zdp.leetcode;
/*
* 问题描述：
* 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:
数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/can-place-flowers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 种花问题 {
    public static void main(String[] args) {
        种花问题 demo = new 种花问题();
        System.out.println(demo.canPlaceFlowers(new int[]{0, 0, 1, 0, 0}, 1));
    }
    //比较常规的解法===> 注意 第一个 和最后一个 其余的时候，只要看两边是否为0即可
    //官方解法好像就是这样子  ===> 将判断条件进行精简了
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        boolean result = false;
        if(flowerbed.length==1)
            if(flowerbed[0]==0)
                return true;
        for(int i=0;i<flowerbed.length&&n>0;i++){
            if(flowerbed[i]==0){
                if(i==0){
                    if(flowerbed[i+1]==0){
                        n--;
                        i++;
                    }
                }else if(i==flowerbed.length-1){
                    if(flowerbed[i-1]==0)
                        n--;
                }else{
                    if(flowerbed[i-1]==0&&flowerbed[i+1]==0){
                        n--;i++;
                    }
                }
            }
        }
        if(n==0)
            result = true;
        return result;
    }
    //官方题解1 使用贪心，思路和我上面是一致的   题解2 就是在题解1的基础上，进行了常数优化===>达到条件就退出循环，不将循环遍历完
    public boolean canPlaceFlowers1(int[] flowerbed, int n) {

        for(int i=0;i<flowerbed.length&&n>0;i++){
            if(flowerbed[i]==0 &&(i==0||flowerbed[i-1]==0)&&(i==flowerbed.length-1||flowerbed[i+1]==0)){
                flowerbed[i] = 1;
                n--;
            }
        }
        if(n<=0){
            return true;
        }
        return false;
    }
}
